package com.lc.lc347;

import java.util.*;

import com.sun.jndi.url.iiopname.iiopnameURLContextFactory;

public class Main {

}

class Solution1 {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> mp = new HashMap<>();
        
        for (int e: nums) {
        	mp.put(e, mp.getOrDefault(e, 0) + 1);
        }
        List<Integer> list = new ArrayList<>(mp.keySet());
        
        list.sort(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return mp.get(o2) - mp.get(o1);
			}
		});
        
        int[] res = new int[k];
        for (int i = 0; i < k; i ++) {
        	res[i] = list.get(i);
        }
        return res;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
    	Map<Integer, Integer> mp = new HashMap<>();
    	for (int e: nums) {
    		mp.put(e, mp.getOrDefault(e, 0) + 1);
    	}
    	
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return mp.get(o1) - mp.get(o2);
			}
		});
        for (int t: mp.keySet()) {
        	queue.offer(t);
        	if (queue.size() > k) {
        		queue.poll();
        	}
        }
        
        int[] ans = new int[k];
        int i = 0;
        for (int e: queue) {
        	ans[i] = e;
        	i++;
        }
        return ans;
    }
}

